#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/4/20 10:01|10:01
# @Author  : yangdingyi
# @File    : 200. 岛屿数量
# @Software: PyCharm
from typing import List


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        n = len(grid)
        if n <= 0:
            return 0
        m = len(grid[0])
        mm = set()
        step = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        ans = 0

        def work(x, y):
            mm.add((x, y))
            for i, p in enumerate(step):
                xx, yy = x + p[0], y + p[1]
                if 0 <= xx < n and 0 <= yy < m:
                    if grid[xx][yy] == '1' and (xx, yy) not in mm:
                        work(xx, yy)

        for i in range(n):
            for j in range(m):
                if grid[i][j] == '1' and (i, j) not in mm:
                    ans += 1
                    work(i, j)

        return ans


solve = Solution()

gg = [
    '11110',
    '11010',
    '11000',
    '00000',
]
print(gg)
print(solve.numIslands(gg))

gg1 = [
    '11000',
    '11000',
    '00100',
    '00011',
]
print(gg1)
print(solve.numIslands(gg1))

